package practice.tree.four;

import jdk.nashorn.internal.ir.WhileNode;
import utils.printer.BinaryTreeInfo;
import utils.printer.BinaryTrees;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/8/22 09:24
 */
//public class HashMap<K, V> implements Map<K, V> {
//    @Override
//    public int size() {
//        return 0;
//    }
//
//    @Override
//    public boolean isEmpty() {
//        return false;
//    }
//
//    @Override
//    public void clear() {
//
//    }
//
//    @Override
//    public V put(K key, V value) {
//        return null;
//    }
//
//    @Override
//    public V get(K key) {
//        return null;
//    }
//
//    @Override
//    public V remove(K key) {
//        return null;
//    }
//
//    @Override
//    public boolean containsKey(K key) {
//        return false;
//    }
//
//    @Override
//    public boolean containsValue(V value) {
//        return false;
//    }
//
//    @Override
//    public void traversal(Visitor<K, V> visitor) {
//
//    }
//    //------------------------------------------------------ 红黑树
//
//    public void print() {
//        if (size == 0) return;
//        for (int i = 0; i < table.length; i++) {
//            final Node<K, V> root = table[i];
//            System.out.println("【index = " + i + "】");
//            BinaryTrees.println(new BinaryTreeInfo() {
//                @Override
//                public Object string(Object node) {
//                    return node;
//                }
//
//                @Override
//                public Object root() {
//                    return root;
//                }
//
//                @Override
//                public Object right(Object node) {
//                    return ((Node<K, V>) node).right;
//                }
//
//                @Override
//                public Object left(Object node) {
//                    return ((Node<K, V>) node).left;
//                }
//            });
//            System.out.println("---------------------------------------------------");
//        }
//    }
//
//    private void fixAfterRemove(Node<K, V> node, Node<K, V> replacement) {
//        if (isRed(node)) return;
//        if (isRed(replacement)) {
//            black(replacement);
//            return;
//        }
//
//        Node<K, V> parent = node.parent;
//        if (parent == null) return;
//
//        boolean left = parent.left == null || node.isLeftChild();
//        Node<K, V> sibling = left ? parent.right : parent.left;
//        if (left) {
//            if (isRed(sibling)) {
//                black(sibling);
//                red(parent);
//                rotateLeft(parent);
//                sibling = parent.right;
//            }
//            if (isBlack(sibling.left) && isBlack(sibling.right)) {
//                boolean parentBlack = isBlack(parent);
//                black(parent);
//                red(sibling);
//                if (parentBlack) {
//                    fixAfterRemove(parent, null);
//                }
//            } else {
//                if (isBlack(sibling.right)) {
//                    rotateRight(sibling);
//                    sibling = parent.right;
//                }
//                color(sibling, colorOf(parent));
//                black(sibling.right);
//                black(parent);
//                rotateLeft(parent);
//            }
//        } else {
//            if (isRed(sibling)) {
//                black(sibling);
//                red(parent);
//                rotateRight(parent);
//                // 更换 sibling
//                sibling = parent.left;
//            }
//            // sibling 左右子节点全是黑色
//            if (isBlack(sibling.left) && isBlack(sibling.right)) {
//                // parent 是否有 RED true 表示没有 RED
//                boolean parentBlack = isBlack(parent);
//                black(parent);
//                red(sibling);
//                if (parentBlack) {
//                    fixAfterRemove(parent, null);
//                }
//            }
//            // sibling 至少有一个红色子节点，将子节点借过来，需要旋转
//            // 一共三种情况，一 sibling.right = RED LR
//            // 二 sibling.left = RED LL
//            // 三 sibling.left and sibling.right = RED LL
//            else {
//                // LR情况
//                if (isBlack(sibling.left)) {
//                    rotateLeft(sibling);
//                    sibling = parent.left;
//                }
//
//                // 由于旋转之后再获取对应的节点会有问题，因此先染色，再旋转
//                color(sibling, colorOf(parent));
//                black(sibling.left);
//                black(parent);
//                rotateRight(parent);
//            }
//        }
//    }
//
//    private void fixAfterPut(Node<K, V> node) {
//        Node<K, V> parent = node.parent;
//        if (parent == null) {
//            black(node);
//            return;
//        }
//        if (isBlack(parent)) return;
//
//        Node uncle = parent.sibling();
//        Node grand = red(parent.parent);
//
//        if (isRed(uncle)) {
//            black(parent);
//            black(uncle);
//            fixAfterPut(grand);
//            return;
//        }
//        if (parent.isLeftChild()) {
//            if (node.isLeftChild()) {
//                black(parent);
//            } else {
//                black(node);
//                rotateLeft(parent);
//            }
//            rotateRight(grand);
//        } else {
//            if (node.isRightChild()) {
//                black(parent);
//            } else {
//                black(node);
//                rotateRight(parent);
//            }
//            rotateLeft(grand);
//        }
//
//    }
//
//    private void rotateLeft(Node<K, V> grand) {
//        Node<K, V> parent = grand.right;
//        Node<K, V> leftChild = parent.left;
//
//        grand.right = leftChild;
//        parent.left = grand;
//        afterRotate(grand, parent, leftChild);
//    }
//
//    private void rotateRight(Node<K, V> grand) {
//        Node parent = grand.left;
//        Node rightChild = parent.right;
//
//        grand.left = rightChild;
//        parent.right = grand;
//        afterRotate(grand, parent, rightChild);
//    }
//
//
//    private Node<K, V> successor(Node<K, V> node) {
//        Node<K, V> s = node.right;
//        if (s != null) {
//            while (s.left != null) s = s.left;
//            return s;
//        }
//        while (node.isRightChild()) node = node.parent;
//        return node.parent;
//    }
//
//    private void afterRotate(Node<K, V> grand, Node<K, V> parent, Node<K, V> child) {
//        parent.parent = grand.parent;
//        if (grand.isLeftChild()) {
//            grand.parent.left = parent;
//        } else if (grand.isRightChild()) {
//            grand.parent.right = parent;
//        } else {
//            table[index(grand.key)] = parent;
//        }
//
//        if (child != null) child.parent = grand;
//        grand.parent = parent;
//    }
//
//    private Node<K, V> black(Node<K, V> node) {
//        return color(node, BLACK);
//    }
//
//    private Node<K, V> red(Node<K, V> node) {
//        return color(node, RED);
//    }
//
//    private Node<K, V> color(Node<K, V> node, boolean color) {
//        if (node == null) return null;
//        node.color = color;
//        return node;
//    }
//
//    private boolean isBlack(Node<K, V> node) {
//        return colorOf(node) == BLACK;
//    }
//
//    private boolean isRed(Node<K, V> node) {
//        return colorOf(node) == RED;
//    }
//
//    private boolean colorOf(Node<K, V> node) {
//        if (node == null) return BLACK;
//        return node.color;
//    }
//
//    private Node<K, V> createNode(K key, V value, Node<K, V> parent) {
//        return new Node<>(key, value, parent);
//    }
//
//    private static class Node<K, V> {
//        int hash;
//        K key;
//        V value;
//        Node left;
//        Node right;
//        Node parent;
//        boolean color = RED;
//
//        public Node(K key, V value, Node parent) {
//            this.key = key;
//            this.value = value;
//            int hash = key == null ? 0 : key.hashCode();
//            this.hash = hash ^ (hash >>> 16);
//            this.parent = parent;
//        }
//
//
//        public boolean isLeftChild() {
//            return parent != null && this == parent.left;
//        }
//
//        public boolean isRightChild() {
//            return parent != null && this == parent.right;
//        }
//
//        public boolean hasTwoChildren() {
//            return this.left != null && this.right != null;
//        }
//
//        public boolean isLeaf() {
//            return this.left == null && this.right == null;
//        }
//
//        public Node sibling() {
//            if (isLeftChild()) return parent.right;
//            if (isRightChild()) return parent.left;
//            return null;
//        }
//
//        @Override
//        public String toString() {
//            return color == RED ? "R_" + key + "_" + value : "B_" + key + "_" + value;
//        }
//    }
//}
